<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3757：苹果树</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">苹果树</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">苹果树</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                苹果树                </h1>
                <p>时间限制：20s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p class="MsoNormal" align="center" style="text-align:center"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">&nbsp; &nbsp; 神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shapetype id="_x0000_t75"
 coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe"
 filled="f" stroked="f">
 <v:stroke joinstyle="miter"/>
 <v:formulas>
  <v:f eqn="if lineDrawn pixelLineWidth 0"/>
  <v:f eqn="sum @0 1 0"/>
  <v:f eqn="sum 0 0 @1"/>
  <v:f eqn="prod @2 1 2"/>
  <v:f eqn="prod @3 21600 pixelWidth"/>
  <v:f eqn="prod @3 21600 pixelHeight"/>
  <v:f eqn="sum @0 0 1"/>
  <v:f eqn="prod @6 1 2"/>
  <v:f eqn="prod @7 21600 pixelWidth"/>
  <v:f eqn="sum @8 21600 0"/>
  <v:f eqn="prod @7 21600 pixelHeight"/>
  <v:f eqn="sum @10 21600 0"/>
 </v:formulas>
 <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
 <o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:4.5pt;
 height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image001.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=6 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image002.gif"
v:shapes="_x0000_i1025"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><span lang="EN-US"><!--[if gte vml 1]><v:shape
 id="_x0000_i1026" type="#_x0000_t75" style='width:4.5pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image001.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]--><!--[if !vml]--><img width="6" height="16" src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image002.gif" v:shapes="_x0000_i1026" alt="" /><!--[endif]--></span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">到</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shape id="_x0000_i1027"
 type="#_x0000_t75" style='width:12.75pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image003.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=17 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image004.gif"
v:shapes="_x0000_i1027"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><span lang="EN-US">n</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">之间的正整数来表示一种颜色。树上一共有</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;">n</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shape id="_x0000_i1028"
 type="#_x0000_t75" style='width:12.75pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image003.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=17 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image004.gif"
v:shapes="_x0000_i1028"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">个苹果。每个苹果都被编了号码，号码为一个</span>1<span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">到</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shape id="_x0000_i1031"
 type="#_x0000_t75" style='width:12.75pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image003.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=17 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image004.gif"
v:shapes="_x0000_i1031"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><span lang="EN-US">n</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">之间的正整数。我们用</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shape id="_x0000_i1032"
 type="#_x0000_t75" style='width:4.5pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image005.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=6 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image006.gif"
v:shapes="_x0000_i1032"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><span lang="EN-US">0</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">代表树根。只会有一个苹果直接根。</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="text-indent: 21.2pt;"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题，才能进屋膜拜神犇。这个问题就是，从树上编号为</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shape id="_x0000_i1033"
 type="#_x0000_t75" style='width:11.25pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image007.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=15 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image008.gif"
v:shapes="_x0000_i1033"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><span lang="EN-US">u</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">的苹果出发，由树枝走到编号为</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shape id="_x0000_i1034"
 type="#_x0000_t75" style='width:11.25pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image009.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=15 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image010.gif"
v:shapes="_x0000_i1034"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><span lang="EN-US">v</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">的苹果，路径上经过的苹果一共有多少种不同的颜色（包括苹果</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shape id="_x0000_i1035"
 type="#_x0000_t75" style='width:11.25pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image007.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=15 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image008.gif"
v:shapes="_x0000_i1035"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><span lang="EN-US">u</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">和苹果</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;">v</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;
mso-bidi-font-family:&quot;Courier New&quot;">的颜色）？不过神犇注意到，有些来膜拜的人患有色盲症。具体地说，一个人可能会认为颜色</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-begin'></span>
QUOTE </span><span lang=EN-US><![if gte vml 1]><v:shape id="_x0000_i1036"
 type="#_x0000_t75" style='width:11.25pt;height:12pt'>
 <v:imagedata src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image011.png"
  o:title="" chromakey="white"/>
</v:shape><![endif]><![if !vml]><img width=15 height=16
src="file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\msohtml1\01\clip_image012.gif"
v:shapes="_x0000_i1036"><![endif]></span><span lang=EN-US style='font-family:
"Courier New"'><span style='mso-spacerun:yes'> </span><span style='mso-element:
field-separator'></span></span><![endif]--><span lang="EN-US">a</span><!--[if supportFields]><span
lang=EN-US style='font-family:"Courier New"'><span style='mso-element:field-end'></span></span><![endif]--><span style="font-family:宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:
&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">就是颜色</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;">b</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;
mso-bidi-font-family:&quot;Courier New&quot;">，那么他们在数苹果的颜色时，如果既出现了颜色</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;">a</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;
mso-bidi-font-family:&quot;Courier New&quot;">的苹果，又出现了颜色</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;">b</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;
mso-bidi-font-family:&quot;Courier New&quot;">的苹果，这个人只会算入颜色</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;">b</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;
mso-bidi-font-family:&quot;Courier New&quot;">，而不会把颜色</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;">a</span><span style="font-family:宋体;
mso-ascii-font-family:&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;
mso-bidi-font-family:&quot;Courier New&quot;">算进来。</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="text-indent: 21.2pt;"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Courier New&quot;;mso-hansi-font-family:&quot;Courier New&quot;;mso-bidi-font-family:&quot;Courier New&quot;">神犇是一个好人，他不会强人所难，也就会接受由于色盲症导致的答案错误（当然答案在色盲环境下也必须是正确的）。不过这样神犇也就要更改他原先数颜色的程序了。虽然这对于神犇来说是小菜一碟，但是他想考验一下你。你能替神犇完成这项任务吗？</span><span lang="EN-US" style="font-family:&quot;Courier New&quot;"><o:p></o:p></span></p>
<p class="MsoNormal" align="left" style="text-indent: 21.2pt;"></p>
<p></p></p><hr/><h3>输入格式</h3><p><div>输入第一行为两个整数n和m，分别代表树上苹果的个数和前来膜拜的人数。</div>
<div></div>
<div>接下来的一行包含n个数，第i个数代表编号为i的苹果的颜色Coli。</div>
<div></div>
<div>接下来有n行，每行包含两个数x和y，代表有一根树枝连接了苹果x和y（或者根和一个苹果）。</div>
<div></div>
<div>接下来有m行，每行包含四个整数u、v、a和b，代表这个人要数苹果u到苹果v的颜色种数，同时这个人认为颜色a就是颜色b。如果a=b=0，则代表这个人没有患色盲症。</div>
<p></p></p><hr/><h3>输出格式</h3><p><p>输出一共m行，每行仅包含一个整数，代表这个人应该数出的颜色种数。</p>
<p></p></p><hr/><h3>样例输入</h3><pre>5 3
1 1 3 3 2
0 1
1 2
1 3
2 4
3 5
1 4 0 0
1 4 1 3
1 4 1 2 
</pre><hr/><h3>样例输出</h3><pre>2
1
2
</pre><hr/><h3>提示</h3><p><div>0&lt;=x,y,a,b&lt;=N</div>
<div>N&lt;=50000</div>
<div>1&lt;=U,V,Coli&lt;=N</div>
<div><span style="font-family: arial, verdana, helvetica, sans-serif; font-size: medium;">M&lt;=100000</span></div>
<div><span style="color: rgb(255, 0, 0);">此题存在版权，故不再支持提交，保留在此只供大家参考题面！ 望见谅！</span></div>
<p></p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3757" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3757" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>